package acm.广东工业大学新生赛;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

//你要不要看看你这什么勾八范围啊
public class N {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int count = sc.nextInt();
        while (count-- > 0) {
            System.out.println(dpFun(sc.nextLong(),sc.nextInt()));
        }
    }
    /**
     * 转dp
     * @param rest
     * @param m
     * @return
     */
    public static long dpFun(long rest,int m){
        long[] dp=new long[(int) (rest+1)];
        dp[0]=1;
        for (int j = 1; j <= m; j++) {
            for (int i = 1; i <=rest; i++) {
                long curr=1<<(j-1);
                if (i>=curr){
                    dp[i]+=dp[(int) (i-curr)];
                    dp[i]=dp[i]%1000000007;
                }
            }
        }
        return dp[(int) rest];
    }
    public static long dpFun2(long rest,int m){
        long[] dp0=new long[Integer.MAX_VALUE];
        long[] dp1=new long[Integer.MAX_VALUE];
        dp0[0]=1;
        for (int j = 1; j <= m; j++) {
            for (long i = 1; i <=rest; i++) {
                long curr=1<<(j-1);
                if (i>=Integer.MAX_VALUE){
                    int k= (int) (i-Integer.MAX_VALUE);
                    if (i>=curr){
                        if (k-curr<0){
                            dp1[k]+=dp0[(int) (i-curr)];
                        }else {
                            dp1[k]=dp1[(int) (k-curr)];
                        }
                        dp1[k]=dp1[k]%1000000007;
                    }
                }
                if (i>=curr){
                    dp0[(int) i]+=dp0[(int) (i-curr)]%1000000007;
                    dp0[(int) i]=dp0[(int) i]%1000000007;
                }
            }
        }
        if (rest>=Integer.MAX_VALUE){
            return dp1[(int) (rest-Integer.MAX_VALUE)];
        }else {
            return dp0[(int) rest];
        }
    }
    /**
     * 当有m种面额可选时，能拿到的最大值
     * @param rest
     * @param m
     * @return
     */
    public static long fun(long rest,int m){
        if (rest==0){
            return 1;
        }
        if (m<1||rest<0){   //没有方案可选
            return 0;
        }
        long res=0;
        long curr=1<<m-1; //当前面额
        res+=fun(rest-curr,m)+fun(rest,m-1);
        return res%1000000007;
    }
//    public static long bigDp(long rest,int m){
//        long[][][] dp=new long[(int) (rest/Integer.MAX_VALUE)+1][Integer.MAX_VALUE][m];
//        Arrays.fill(dp[0][0],1);
//        for (long i = 1; i <=rest; i++) {
//            for (int j = 1; j <= m; j++) {
//                long curr=1<<(j-1);
//                if (i>=curr){
//                    dp[(int) (i/Integer.MAX_VALUE)][(int) (i%Integer.MAX_VALUE)][j]
//                            =dp[(int) ((i-curr)/Integer.MAX_VALUE)][(int) ((i-curr)%Integer.MAX_VALUE)][j];
//                }
//                dp[(int) (i/Integer.MAX_VALUE)][(int) (i%Integer.MAX_VALUE)][j]
//                        =(dp[(int) (i/Integer.MAX_VALUE)][(int) (i%Integer.MAX_VALUE)][j]
//                        +dp[(int) (i/Integer.MAX_VALUE)][(int) (i%Integer.MAX_VALUE)][j-1])%1000000007;
//            }
//        }
//        return dp[(int) (rest/Integer.MAX_VALUE)+1][(int) (rest%Integer.MAX_VALUE)][m];
//    }

    static {
        System.out.println(fun(1, 1));
        System.out.println(dpFun(5, 2));
//        compare();
    }
    public static void compare(){
        long s=1000000000000000000L;
        int count=1000;
        Random r=new Random();
        while (count-- > 0) {
            int n = r.nextInt(100) + 1;
            int m = r.nextInt(15) + 1;
            long dpFun = dpFun(n, m);
            long fun = fun(n, m);
            if (dpFun!=fun){
                System.out.println(n+":"+m);
                System.out.println("预期:"+fun+"\t实际"+dpFun);
            }
        }
        System.out.println("dssd");
    }
}